package developer.算法.链表.环形链表;

/**
 * @author zhangyongkang
 * @since 2024/7/8 19:53
 */
public class Solution_other {

    /**
     * 作者：力扣官方题解
     * 链接：https://leetcode.cn/problems/linked-list-cycle/solutions/440042/huan-xing-lian-biao-by-leetcode-solution/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     * <p>
     * 为什么我们要规定初始时慢指针在位置 head，快指针在位置 head.next，而不是两个指针都在位置 head（即与「乌龟」和「兔子」中的叙述相同）？
     * <p>
     * 观察下面的代码，我们使用的是 while 循环，循环条件先于循环体。由于循环条件一定是判断快慢指针是否重合，如果我们将两个指针初始都置于 head，那么 while 循环就不会执行。因此，我们可以假想一个在 head 之前的虚拟节点，慢指针从虚拟节点移动一步到达 head，快指针从虚拟节点移动两步到达 head.next，这样我们就可以使用 while 循环了。
     * <p>
     * 当然，我们
     * <p>
     * 作者：力扣官方题解
     * 链接：https://leetcode.cn/problems/linked-list-cycle/solutions/440042/huan-xing-lian-biao-by-leetcode-solution/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     * <p>
     * 快慢指针（乌龟兔子）
     * 兔子肯定>乌龟
     * 如果没有闭环  那么他们两个永远不会相遇
     * 如果乌龟和兔子相遇了
     * 说明乌龟被兔子套圈了
     * 有闭环！
     */


    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    class Solution {
        public boolean hasCycle(ListNode head) {
            if (head == null || head.next == null) return false;
            ListNode slowNode = head;
            ListNode fastNode = head.next;

            while (fastNode != slowNode) {
                if (fastNode == null || fastNode.next == null) return false;
                slowNode = slowNode.next;
                fastNode = fastNode.next.next;
            }
            return true;
        }

    }

}
